n=1999;
bracket=[")",")",")","(","(","(","(",")","(","(",")","(",")","(",")","(","(",")",")",")","(",")",")","(","(","(",")","(",")","(",")","(","(",")",")",")","(","(","(","(",")","(",")",")","(",")",")",")",")",")",")",")",")",")","(","(",")","(",")",")",")","(","(","(","(",")",")","(","(","(",")",")",")",")",")","(",")",")","(","(","(",")","(","(",")",")","(",")","(","(","(","(",")",")",")",")",")",")","(",")","(","(",")",")","(",")","(","(","(","(",")",")","(","(","(","(","(",")",")",")",")","(","(",")","(",")",")",")",")","(",")",")",")",")",")","(",")","(","(","(",")","(","(","(","(","(","(",")","(","(","(","(",")",")",")","(",")",")","(","(",")","(","(",")","(","(",")",")",")","(","(","(",")","(",")","(",")","(",")","(",")","(","(",")","(","(",")",")","(","(","(","(","(",")",")",")","(",")",")","(","(",")",")","(","(","(","(","(",")","(",")","(",")","(","(","(",")","(","(",")","(",")","(",")",")","(",")","(","(","(","(",")","(","(",")",")",")","(","(","(",")","(",")",")","(","(","(","(","(","(","(",")","(","(",")",")",")",")","(",")","(",")",")",")",")",")",")",")","(","(","(","(","(","(","(",")","(","(","(",")",")","(",")","(",")",")","(",")",")","(",")",")","(","(",")","(","(","(",")","(",")","(",")","(","(",")","(",")","(","(",")","(",")",")",")",")",")",")",")",")","(","(",")",")",")","(",")","(",")",")",")",")","(","(",")",")","(","(",")",")",")",")","(",")",")","(",")",")","(","(","(",")",")","(","(",")",")","(","(",")","(",")","(",")","(","(","(",")",")","(",")","(",")","(","(",")",")",")","(",")","(",")",")","(","(","(","(",")",")",")",")","(",")","(",")","(",")","(","(","(",")","(",")",")",")","(","(","(","(",")","(",")",")","(","(","(","(",")","(","(","(",")","(","(","(","(","(",")",")",")","(",")",")","(","(",")",")",")","(",")",")",")",")",")",")",")","(","(",")","(",")","(","(","(","(",")",")",")",")",")",")","(","(",")",")",")","(","(",")",")","(",")","(","(",")","(","(","(",")",")",")",")","(","(",")",")",")",")",")",")","(","(",")",")","(",")",")",")","(",")","(",")",")",")",")",")","(","(","(","(","(",")","(","(","(","(","(","(",")",")",")","(","(",")","(",")",")","(","(",")","(",")",")","(",")",")","(","(",")",")",")","(",")","(",")",")","(",")","(","(",")","(",")","(","(","(","(",")",")",")",")","(",")",")",")",")","(","(","(","(","(","(",")",")","(","(",")",")","(","(","(","(","(","(",")",")",")","(",")",")",")",")","(",")","(","(","(",")",")",")","(","(",")","(","(","(",")","(","(","(","(",")",")",")","(",")",")","(",")","(","(",")","(",")",")",")","(","(",")","(",")","(",")",")","(",")","(","(","(",")","(",")",")","(",")","(",")","(",")",")",")","(",")","(","(",")",")",")",")",")","(",")",")","(",")","(","(","(",")","(","(","(","(","(","(",")",")","(","(",")","(","(","(","(",")",")","(",")",")","(","(","(","(","(",")","(",")",")",")",")","(","(",")",")",")","(",")",")",")","(",")","(",")","(",")","(","(","(","(","(","(",")",")",")","(","(",")","(","(",")",")",")",")",")",")",")","(","(","(","(",")","(",")","(","(",")",")",")","(","(",")",")",")",")","(","(","(","(","(",")","(","(",")","(","(","(",")",")",")","(","(",")",")","(","(","(","(","(",")",")","(",")","(","(",")",")",")",")","(","(",")",")",")","(",")","(",")",")","(",")","(",")",")","(","(",")","(",")","(","(","(",")","(",")","(","(",")",")","(","(","(",")","(",")","(","(","(","(","(","(","(",")","(","(",")","(","(","(","(","(",")",")","(","(",")","(",")",")","(",")","(",")",")","(",")","(",")",")",")",")","(","(",")",")",")",")","(",")","(","(","(","(","(",")",")",")","(","(",")",")","(",")","(","(","(","(",")","(","(",")","(",")","(",")","(","(",")",")","(",")","(",")","(","(","(",")","(",")","(","(","(",")","(",")","(",")","(","(",")","(","(","(","(",")","(",")","(",")","(","(",")",")","(","(","(",")","(",")","(",")",")",")",")","(",")","(",")","(",")",")",")","(","(",")","(","(",")","(","(","(",")","(",")","(",")","(",")",")",")","(",")",")","(","(","(","(",")","(",")","(","(","(",")","(","(",")",")","(","(","(","(","(",")","(",")",")",")",")",")",")","(","(",")",")",")",")","(",")","(",")","(","(","(",")",")",")",")",")","(","(","(",")",")","(","(",")","(",")","(",")",")",")","(","(","(","(","(",")","(",")",")","(","(","(","(","(","(","(","(","(",")",")","(",")","(","(",")","(","(","(","(","(",")",")",")","(","(","(","(",")",")",")","(","(","(",")","(","(","(",")",")","(","(","(","(",")",")",")","(","(","(",")","(","(",")","(",")","(","(",")",")","(",")","(",")","(",")","(",")","(",")",")","(","(",")",")","(",")",")","(",")",")","(","(","(",")",")",")","(","(",")","(",")",")","(","(","(","(",")",")",")",")",")","(","(",")",")","(","(",")",")","(",")","(",")",")","(",")",")","(",")",")",")",")",")","(","(","(",")",")","(","(",")",")",")",")",")",")","(","(","(","(",")","(",")",")","(",")","(","(","(","(","(","(","(","(","(","(","(","(","(",")",")","(",")","(","(","(","(",")",")",")","(","(",")",")","(","(",")",")","(","(","(",")",")","(",")","(",")","(","(","(","(","(",")",")",")",")","(",")",")","(",")",")",")",")",")",")",")",")",")","(","(",")","(","(","(","(","(","(",")",")",")",")","(",")",")",")",")","(",")","(",")",")","(","(","(","(","(","(","(","(",")",")","(","(","(",")","(",")","(","(",")","(","(",")",")","(",")",")",")",")","(","(",")",")",")","(","(","(",")",")",")",")",")",")",")",")",")","(",")",")",")","(","(",")","(","(","(","(",")",")","(","(","(","(",")","(","(","(",")","(",")",")",")",")",")",")",")","(","(","(","(","(",")",")","(","(",")","(",")",")","(","(","(",")",")","(","(","(","(","(","(","(","(","(","(",")","(",")","(",")","(",")","(","(",")","(",")",")",")",")",")","(","(",")","(","(","(",")","(",")","(",")","(",")","(","(",")",")","(","(",")",")","(","(","(",")",")","(",")",")","(","(","(",")","(",")","(",")",")",")","(","(",")",")",")","(","(",")","(",")",")","(",")","(","(","(","(","(",")",")",")","(","(","(","(",")",")","(",")",")","(","(",")",")",")",")","(","(",")","(",")",")",")",")",")","(",")","(","(",")","(","(",")",")",")","(",")",")",")","(","(",")",")","(",")",")","(","(",")","(",")",")",")","(",")",")",")",")","(","(","(","(",")","(","(","(",")",")","(","(","(",")","(","(","(","(",")",")",")",")",")","(",")",")",")",")",")",")","(","(",")",")",")",")","(",")","(","(",")","(",")","(","(","(",")","(",")",")","(","(",")","(",")",")","(",")","(","(",")",")","(",")",")","(","(","(","(",")",")","(","(","(",")","(",")","(",")","(","(","(",")",")","(",")",")",")",")","(",")",")","(","(","(","(",")",")",")",")",")","(","(",")",")",")","(",")","(","(","(",")",")","(",")","(","(","(",")","(",")",")",")",")","(","(","(","(","(",")","(","(","(","(","(","(","(",")","(",")","(","(",")",")",")","(","(",")",")","(","(",")","(","(",")",")",")",")",")","(",")","(","(","(",")",")",")","(","(","(","(",")",")",")",")","(","(",")","(","(","(",")","(","(",")",")","(",")",")","(",")",")","(","(","(","(","(","(","(",")",")",")","(","(",")","(",")","(","(","(",")","(","(",")",")","(",")","(",")",")","(",")",")",")","(","(","(",")",")",")","(",")","(",")","(","(","(","(","(","(",")","(",")",")","(",")","(","(","(","(","(",")","(","(",")",")",")",")","(",")",")",")","(","(",")",")","(","(",")",")",")",")","(",")",")","(",")",")",")",")","(",")",")","(","(","(","(",")","(",")",")","(",")","(","(",")",")",")",")",")",")",")",")","(","(","(",")","(","(","(","(",")","(",")","(",")","(","(",")",")","(","(","(",")",")",")",")",")",")",")",")",")","(","(",")",")",")",")","(","(","(","(","(",")","(","(","(",")",")","(",")","(",")","(","(","(",")",")","(",")",")",")","(","(","(","(","(","(","(","(",")","(",")","(","(","(",")",")","(",")",")","(",")",")",")","(","(",")","(","(","(",")","(",")","(",")","(","(","(",")",")","(","(",")",")","(","(","(","(",")","(","(","(","(",")","(","(","(",")",")",")","(",")","(","(",")","(",")","(",")",")","(","(",")","(",")","(",")","(",")",")",")",")","(",")",")",")","(","(",")","(",")","(",")","(",")",")","(",")","(","(","(",")","(","(","(","(",")","(",")",")","(",")",")",")",")",")",")","(",")","(","(",")",")","(","(","(","(",")"];
father=[1,1,3,3,1,2,5,6,9,10,5,9,6,14,3,9,12,16,18,6,17,2,3,2,20,8,6,23,20,28,22,30,12,16,15,30,33,26,16,3,28,21,18,28,18,37,21,23,21,41,6,1,53,49,10,55,2,37,47,48,32,17,51,4,14,32,53,62,60,62,67,64,59,68,71,34,33,19,61,50,16,30,77,55,28,21,65,72,78,14,22,33,3,57,38,27,50,24,32,80,91,33,36,29,16,20,38,84,104,43,69,63,99,88,73,63,109,65,82,85,96,53,88,112,96,28,104,94,32,82,38,38,21,81,114,136,95,115,89,74,89,103,77,119,17,118,57,52,68,143,81,70,66,92,1,108,128,120,135,117,76,116,19,93,135,69,2,164,154,41,142,164,57,6,42,53,170,159,122,170,179,27,62,135,116,71,105,80,70,29,7,176,146,62,37,94,98,93,68,89,136,87,4,136,7,32,132,130,35,108,129,8,24,106,185,4,76,36,96,57,171,30,174,113,56,81,63,193,173,20,47,195,27,43,80,129,158,107,89,21,75,1,135,208,132,48,97,124,220,185,26,82,241,4,211,58,50,84,44,4,48,190,24,219,259,171,34,26,117,219,259,184,273,48,233,58,34,189,73,47,208,209,196,238,71,109,169,92,121,263,287,61,160,245,179,228,98,275,80,91,92,48,300,85,255,206,251,25,28,51,93,288,303,206,119,263,134,57,198,206,35,250,70,151,290,130,130,37,33,264,151,233,64,4,227,14,182,112,164,118,77,287,199,37,132,103,158,225,150,46,116,194,342,98,181,303,353,200,107,55,354,273,303,7,71,119,2,74,368,118,92,61,145,345,11,337,218,161,81,157,369,30,197,353,287,209,228,200,371,326,262,359,99,295,75,279,342,1,145,120,240,250,357,232,387,275,199,322,45,408,233,141,104,269,162,162,91,94,49,150,22,121,295,321,114,193,241,408,149,373,391,251,276,157,22,324,128,418,249,211,108,43,133,130,419,296,210,17,203,48,348,327,130,191,246,293,449,84,312,396,407,4,163,387,219,37,232,152,360,253,32,113,306,124,102,188,229,401,351,53,163,290,169,18,292,382,266,111,443,213,238,358,1,377,410,183,9,420,234,345,170,425,334,489,323,126,30,61,418,445,288,71,412,384,317,164,397,452,258,200,471,439,195,464,139,274,192,238,511,359,386,123,123,76,264,7,128,222,43,333,445,383,11,528,156,109,101,240,427,365,8,513,308,76,3,244,384,146,223,240,428,228,98,313,469,312,189,170,343,511,65,368,204,301,136,222,102,203,38,102,59,511,270,266,360,228,545,431,561,204,364,252,196,471,189,234,593,255,539,210,17,409,292,6,546,409,411,71,507,439,433,577,303,301,157,524,612,60,106,382,522,142,366,180,225,88,510,388,105,66,161,481,237,246,31,556,332,239,209,612,606,55,97,84,102,29,427,552,67,497,324,94,563,579,469,185,314,177,61,482,504,417,438,450,21,31,461,8,516,475,325,150,493,209,71,44,105,570,487,562,110,513,167,587,488,325,468,455,57,517,578,156,170,475,561,292,204,502,156,402,565,392,670,694,641,633,572,25,545,386,352,105,268,263,251,613,546,464,317,339,406,276,205,518,190,673,424,329,598,368,69,127,276,620,409,400,113,160,101,200,468,392,313,323,648,337,36,523,338,706,668,59,451,31,511,85,234,332,572,437,361,584,90,287,552,250,434,367,500,438,355,429,559,637,621,249,64,661,324,638,278,503,80,423,477,275,244,571,326,406,316,197,360,640,762,242,246,180,457,53,322,241,349,178,171,595,606,268,383,256,285,802,448,423,697,767,274,774,253,162,767,650,515,584,198,465,2,114,659,571,19,669,285,149,481,527,82,391,300,157,839,627,755,567,58,277,726,487,658,250,784,412,581,723,209,686,702,343,774,399,116,840,458,734,669,510,626,365,515,790,349,663,530,310,761,683,846,191,868,107,175,196,121,149,205,263,181,726,523,320,417,594,161,791,423,325,757,645,899,608,349,493,66,159,18,451,364,423,7,726,400,741,73,738,335,786,205,498,644,507,412,280,174,231,181,267,208,518,651,761,911,188,83,894,122,704,141,467,583,645,131,830,347,298,59,911,30,241,807,199,243,174,172,667,716,78,468,908,553,229,144,687,947,746,684,850,241,756,699,912,808,304,86,255,382,749,962,715,738,571,554,137,62,677,871,113,975,356,4,62,606,467,447,640,380,453,756,252,734,120,252,851,364,763,835,476,339,814,656,694,748,417,134,745,324,179,177,202,730,528,984,285,130,106,598,575,517,872,434,657,205,304,85,675,223,1007,424,680,825,960,664,645,881,127,514,871,818,797,236,42,735,571,199,521,943,902,803,825,490,60,280,527,861,147,234,140,842,468,591,1051,201,66,1013,850,802,349,455,1055,315,114,680,950,108,605,256,321,453,872,482,303,952,903,482,149,332,545,996,105,631,443,539,338,1081,434,290,344,364,158,253,301,41,607,1031,1090,812,550,355,34,30,534,822,962,949,205,1059,316,748,1104,276,74,531,125,810,66,117,831,877,69,159,649,1114,849,138,977,756,763,235,801,459,866,514,1055,511,871,578,95,772,740,925,1008,565,874,526,897,550,956,741,38,280,445,495,921,354,883,1089,875,750,787,820,1169,554,457,59,9,238,714,1187,57,777,499,115,654,983,717,798,1165,1160,731,513,894,550,118,732,871,903,67,218,120,156,100,618,171,759,1,263,172,980,607,463,353,670,21,319,814,1062,943,939,434,774,454,80,89,695,773,540,698,675,318,524,619,510,1113,578,10,524,371,1103,19,775,735,848,353,1032,540,900,1009,1065,1237,1023,1257,968,868,1037,684,821,405,326,246,843,1128,266,747,547,7,72,389,52,629,1272,1067,423,370,429,29,781,540,1062,1172,1261,434,520,1144,688,1077,1273,185,183,568,576,225,762,206,616,434,315,974,642,54,549,430,344,232,708,582,343,1052,1069,840,1062,1034,724,987,596,137,949,732,33,228,587,1103,876,431,289,130,390,18,922,278,1018,893,797,958,590,218,5,1,1145,703,949,408,1241,598,489,983,702,664,134,59,1130,354,1174,1110,611,477,844,590,371,126,360,127,1241,1172,418,1032,1076,745,981,7,853,426,848,775,1163,1109,399,391,203,127,1125,623,1326,680,807,1198,584,1251,67,1280,1118,880,427,444,984,459,379,55,1264,262,610,632,291,1235,1244,856,1208,603,1367,625,1365,533,675,628,1107,1090,191,284,314,1104,813,1040,942,166,362,197,649,323,1108,1299,371,417,119,5,1112,364,608,1310,1403,357,266,683,137,793,799,1144,1332,1209,400,662,1103,330,304,184,478,989,1368,1433,326,1148,389,1016,998,529,379,275,1065,1019,500,666,312,303,1221,405,1201,1056,196,1347,1033,282,961,207,1193,270,1348,1292,720,957,1028,642,51,97,148,539,738,1353,453,1415,1443,1212,481,871,1190,962,778,1030,70,84,104,436,340,136,473,870,169,713,874,1429,1226,336,227,1026,926,719,714,1322,810,743,879,855,525,1500,1148,1372,153,1515,694,1385,954,27,625,852,13,169,713,438,610,1057,1537,1281,859,302,1180,1203,1465,117,929,887,597,423,1250,983,948,1221,697,900,166,345,898,1472,636,1165,48,980,820,326,1269,1391,309,701,1317,561,1196,1080,38,793,263,228,913,1199,555,736,822,1318,381,1107,717,1265,22,287,465,867,799,280,328,442,1018,776,689,1425,439,1301,654,521,1026,883,1169,982,1370,1277,950,292,1546,693,211,786,295,19,664,573,1575,337,155,432,497,148,235,132,186,1142,1084,1005,1160,683,1018,266,444,889,942,1333,1126,423,90,1116,1138,1520,457,628,827,1446,1179,695,597,735,349,1557,1149,176,551,564,567,578,1082,579,1518,1067,1039,794,1297,233,1065,1081,290,1314,743,916,1178,158,310,1173,1479,1390,1257,912,386,127,1144,146,405,1231,480,1574,1134,951,1254,1429,1035,394,223,1386,663,41,229,1558,1393,1524,1423,613,604,1417,854,743,808,358,1476,401,1338,1565,235,823,1247,1673,629,600,1501,1579,1283,1228,1466,1033,360,147,270,408,1700,851,1017,306,1654,246,1339,477,1150,573,1585,64,356,519,338,217,82,1210,1492,1230,532,1042,812,486,21,1308,991,1249,746,10,1356,320,288,1632,109,920,1145,106,263,1601,950,579,69,7,1051,999,1453,1705,1,574,355,730,1509,29,1189,1546,912,1604,1614,1400,70,1459,1056,121,1687,1740,1700,936,1646,520,1213,41,18,45,834,786,1437,1783,1095,1312,580,725,1232,1384,1788,1271,7,899,78,593,1159,202,531,723,863,402,922,960,1406,1580,1751,892,95,843,418,1378,583,1338,1377,1242,1026,399,1479,1537,359,139,463,66,421,560,470,41,1434,65,686,1033,389,222,153,986,1636,1812,457,709,351,34,1075,1334,498,741,1089,1195,723,398,1380,164,269,73,237,984,661,1613,925,1068,533,635,612,1522,1543,177,564,651,658,423,1801,1884,611,1084,1819,744,678,293,1904,1320,349,482,761,1497,1825,1705,1804,1079,543,951,1219,1913,849,1458,1236,479,1223,212,1374,1138,1808,278,1197,1599,12,542,520,962,1782,1237,212,1229,1185,1173,462,957,1473,754,1631,783,1581,158,1197,1849,1964,150,1408,1123,1895,1121,1771,1434,621,841,1704,1297,587,1663,98,153,1577,327,165,1804,422,1123,462,1211,1681,1836,873,1379];